package com.gyg.程序员面试金典;

/**
 * Definition for singly-linked list.
 * class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) {
 * val = x;
 * next = null;
 * }
 * }
 */

import java.util.HashSet;
import java.util.Set;

/**
 * 面试题 02.08. 环路检测
 */
public class T02_08 {


    /**
     * 使用HashSet来做
     * 解题思路：hashset判断节点是否重复
     * （1）首先判断链表是否为空或长度为1，如果是则一定不是有环链表
     * （2）利用hashset存储每一个不重复的节点
     * （3）循环遍历整个链表，如果存在回环的话，中间一定有一个节点的next指向之前遍历过的节点，
     * （4）如果发现某一个节点的是之前的节点，说明该节点是回环起始点
     * （5）如果该节点不在hashset中就存储，就添加到hashset中，继续遍历下一个节点，
     * （6）循环结束条件：找到重复节点。或链表遍历完毕
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
//        （1）首先判断链表是否为空或长度为1，如果是则一定不是有环链表
        if (head == null || head.next == null) {
            return null;
        }
//        （2）利用hashset存储每一个不重复的节点
        Set<ListNode> sets = new HashSet<ListNode>();
//        （3）循环遍历整个链表，
        while (head != null) {
//           （4） 如果存在回环的话，中间一定有一个节点的next指向之前遍历过的节点，
            if (sets.contains(head)) {
//              （5）  如果发现某一个节点的是之前的节点，说明该节点是回环起始点
//                返回回环起始点
                return head;
            } else {
//                （6）如果该节点不在hashset中就存储
                sets.add(head);
//                （7）继续遍历下一个节点
                head = head.next;
            }
        }
        return null;
    }


    /**
     * 快慢指针法
     * 解题思路：利用从相遇点到入环点的距离加上 n−1n-1n−1 圈的环长，恰好等于从链表头部到入环点的距离。
     * （1）定义一个慢链表，一个快链表，来接收head链表
     * （2）循环两个链表，如果快链表遍历到最后一个节点，就退出循环
     * （3）让慢链表每次只走一步，让快链表每次走两步
     * （4）如果慢指针和快指针相遇了，就说明存在回环，但相遇点不一定是起始回环点
     * （5）使用一个新的链表来接收head，重新开始往下走
     * （6）让旧的链表和新的链表一起走，当他们相遇时的节点，就是回环起始节点
     * （7）此时返回回环起始节点
     *
     * @param head
     * @return
     */
    public ListNode detectCycle_2(ListNode head) {
//        （1）定义一个慢链表，一个快链表，来接收head链表
        ListNode slowNode = head;
        ListNode fastNode = head;
//        （2）循环两个链表，如果快链表遍历到最后一个节点，就退出循环
//        如果存在最后一个节点，说明一定不是回环链表
        while (fastNode != null && fastNode.next != null) {
//            （3）让慢链表每次只走一步
            slowNode = slowNode.next;
//            （4）让快链表每次走两步
            fastNode = fastNode.next.next;
//            （5）如果慢指针和快指针相遇了，就说明存在回环，但相遇点不一定是起始回环点
            if (slowNode == fastNode) {
//                （6）使用一个新的链表来接收head，重新开始往下走
                ListNode pirNode = head;
//                （7）让旧的链表和新的链表一起走，当他们相遇时的节点，就是回环起始节点
//                从相遇点到入环点的距离加上 n−1n-1n−1 圈的环长，恰好等于从链表头部到入环点的距离。
                while (pirNode != slowNode) {
                    pirNode = pirNode.next;
                    slowNode = slowNode.next;
                }
//                （8）此时返回回环起始节点
                return pirNode;
            }
        }
        return null;
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
